package com.lun.swordtowardoffer2.c13;

import java.util.ArrayList;
import java.util.List;

public class CombinationSum {

	public List<List<Integer>> combinationSum(int[] nums, int sum){
		List<List<Integer>> result = new ArrayList<>();
		List<Integer> path = new ArrayList<>();
		backtracking(nums, sum, 0, 0, path, result);
		return result;
	}
	
	private void backtracking(int[] nums, int sum, int currentSum, int startIndex, // 
			List<Integer> path, List<List<Integer>> result) {
		
		if(sum <= currentSum) {
			if(sum == currentSum) {
				result.add(new ArrayList<>(path));
			}
			return;
		}
		
		for(int i = startIndex; i < nums.length; i++) {
			path.add(nums[i]);
			backtracking(nums, sum, currentSum + nums[i], i, path, result);
			path.remove(path.size() - 1);
		}
	}
	//sum,currentSum 可合并成一个参数target = sum - currentSum
}
